1. Field of Invention
This invention relates to systems and methods for solving nogood databases associated with a Boolean system of prepositional variables.
2. Description of Related Art
Constraint satisfaction problems involve the assignment of values to variables subject to a set of constraints. The set of constraints are an expression of knowledge about the variables and their relationships. Solving a constraint satisfaction problem involves finding a set of values for the variables that simultaneously satisfy the set of constraints. Constraint satisfaction problems include, for example, map coloring, understanding line drawings, electronic circuit analysis, and truth maintenance systems.
Many different approaches for solving constraint problems are known. For example, Freuder, “A Sufficient Condition for Backtrack-Bounded Search”, Journal of the Association for Computing Machinery, Vol. 32, No. 4, pp. 755–761, Oct. 1985, incorporated herein by reference in its entirety, discusses an approach to bounding the backtracking of a backtrack search. Dechter et al., “Network-based Heuristics for Constraint-Satisfaction Problems”, Artificial Intelligence, 34, pp. 1–38, 1988, also incorporated herein by reference in its entirety, discusses a method of generating heuristic advise to guide the order of value assignments in solving constraint satisfaction problems. See also U.S. Pat. Nos. 5,438,511, 5,727,222, 5,819,210, 5,903,860 and 6,064,953, each of which is incorporated herein by reference in its entirety.